There are many contemporary known methods of encoding data (D1) to generate encoded data (E2), and also decoding the encoded data (E2) to generate decoded data (D3). Nevertheless, there is a lack of a method of encoding data which is suitable for a broad range of content represented by the data (D1) to be encoded, for example still images, video content, audio content or graphics data. Such encoding has as its primary aim to generate encoded data (E2) that is more compact than corresponding data (D1) to be encoded. Moreover, there is also a lack of a corresponding decoder for decoding such encoded data (E2).
Image encoding methods such as JPEG (“Joint Photographic Experts Group”, namely lossy DCT-based coding, wherein “DCT” is an abbreviation for Discrete Cosine Transform), JPEG2000 (“Joint Photographic Experts Group”, namely wavelet-based encoding) and WebP (image format encoding which employs both lossy and lossless compression during encoding) are known to be well adapted for compressing natural image content, but are less suitable for compressing text or images whose colours are described by only a few colour values and whose content has a relatively high spatial frequency component. An alternative known method of encoding data is referred to as GIF (“Graphics Interchange Format”) and employs a palette-based compression algorithm which is well adapted to encode images that can be presented with a relatively small number of colour values required to render the images, for example 256 colour values; however, if the images to be encoded by GIF algorithms include natural objects having subtle spatially-gradual colour variations, GIF creates undesirable artefacts which are noticeable in corresponding decoded GIF images. Known contemporary PNG encoding (“Portable Networks Graphics”, lossless encoding) is generally similar to GIF encoding and provides more options for encoding image data, but is not nevertheless well adapted for images which contain a small range of colour values. Other known encoding methods employ text encoding using OCR (“Optical Character Recognition”) in combination with encoding characters; OCR is sometimes an appropriate method to employ, but is sensitive to positioning of text within an image, tilting of the text within the image, a font of the text and also an object in which the text is located; additionally, OCR can potentially require considerable processing power for its implementation.
More recently, scientific publications have proposed further alternative encoding methods which are suitable for encoding data that is in a bi-level block data sequence format; details of these scientific publications are provided in Table 1.
TABLE 1Encoding methods for encoding data in a bi-level block data sequence format.Title of publicationAuthorsPublication details“A bi-level block codingLi Tan andProceedings of the 2008 IAJC-IJMEtechnique for encodingJean JiangInternational Conference, Internationaldata sequences with sparseJournal of Modern Engineering (IJME), paperdistribution”185, ENT 201.ISBN 978-1-60643-379-9“Lossless compression ofS. D. Stearms,IEEE Transactions on Geoscience andwaveform data forL. Tan, andRemote Sensing,efficient transmission andN. MagotraVol. 31, no. 3, pp 645-654, May 1993storage”“A block coding techniqueG. Zeng andIEEE Transactions on Acoustics, Speech andfor encoding sparse binaryN. AhmedSignal Processing,patterns”Vol. 37, no. 5, pp 778-780, May 1989
Aforesaid known methods of encoding data, and corresponding known methods of decoding such encoded data, are not well adapted for a broad range of content represented by the data, despite the known methods employing a wide range of mutually different approaches. Despite considerable research over many years to evolve more efficient encoding algorithms to provide improved data compression, namely an issue of great importance to communication systems handling streamed video content, an optimal encoding method has yet to be devised.
U.S. Pat. No. 6,151,409 (“Methods for Compressing and Reconstructing a Color Image in a Computer System”; Applicant—National Science Council, Taipei, Taiwan) recites a method of compressing a colour image, namely by employing visual block pattern truncation coding (VBPIC), in which conventional block truncation coding (BTC) serves to encode an original image. The method defines an edge block according to human visual perception. In an event that a difference between two quantized values of BTC in a block is larger than a threshold value which is defined by visual characteristics, the block will be identified as an edge block. In an edge block, the bitmap is adapted to compute block gradient orientation and to match the block pattern.
The method is only barely suitable for an image that contains only 4×4 blocks which further contain either a DC level or a clear edge at an angle of 90° or 45°. Moreover, the method is capable of removing noise, or is capable of removing details when the mask does not hit the target exactly. Furthermore, the method is not at all suitable for coding text or texture, and is not suitable for coding patterns that cannot be expressed with a straight line, or that have a different direction from multiples of 45°.
U.S. Pat. No. 5,668,932 (“Digital Video Data Compressions Technique”, Applicant—Microsoft Corporation) recites an alternative technique for compressing digital video data that provides improved compression relative to conventional block compression techniques. In the alternative technique, image data is broken down into cells and iteratively compressed. The cells are compressed using compression formats that are most appropriate for the contents of the cells. A determination is first made whether or not a cell is substantially identical to a succeeding cell in a previous frame. If the cell is substantially identical to the cell in the previous frame, the cell is encoded in compressed form as a duplicate of the previous cell. Moreover, solid-colour compression approaches and eight-colour compression approaches may be integrated into the compression technique.
Thus, the method uses a bit mask which conveys whether a given pixel being processed belongs to a higher value, namely brighter pixels, or to a lower value, namely dimmer pixels, for each block, cell or sub-block. Moreover, the method attempts to encode entire images.
Published PCT application WO 00/19374 (“Compressing and Decompression Image Data with 4-level Block Coding”, Applicant—Silicon Graphics Inc.) recites a method and an apparatus for compressing and uncompressing image data. Optionally, the method of compressing a colour cell comprises steps of:
(i) defining at least four luminance levels of the colour cells;
(ii) generating a bitmask for the colour cells, wherein the bitmask has a plurality of entries each corresponding to a respective one of the pixels, and each of the entries for storing data identifying one or the luminance levels associated with a corresponding one of the pixels;
(iii) calculating a first average colour of pixels associated with a first one of the luminance levels;
(iv) calculating a second average colour of pixels associated with a second one of the luminance levels; and
(v) storing the bitmask in association with the first average colour and the second average colour.
Optionally, the colour cell includes a matrix of 4×4 pixels, the bitmask includes 32-bits, and each of the colour values include I6-bits, such that a compression rate of 4-bits per pixel is achievable. The method is applicable to compress texture data, such that the texture data is capable of being more efficiently cached and moved during texture mapping; compression of luminance, intensity and alpha textures are also possible to be achieved.
Moreover, aforementioned known coding methods have various shortcomings which makes them unsuitable for a wide spectrum of types of data.